import java.util.ArrayList;
import java.util.Arrays;

/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class MergeIntervals {

	class Interval implements Comparable<Interval> {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}

		@Override
		public int compareTo(Interval o) {
			if (o.start < start) {
				return 1;
			}
			return -1;
		}
	}

	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
		ArrayList<Interval> res = new ArrayList<Interval>();
		int n = intervals.size();
		if (n == 0)
			return res;
		Interval[] in = new Interval[n];
		intervals.toArray(in);
		Arrays.sort(in);
		for (int i = 0; i < n;) {
			int j = i + 1;
			int max = in[i].end;
			while (j < n && in[j].start <= max) {
				max = Math.max(max, in[j].end);
				j++;
			}
			in[i].end = max;
			res.add(in[i]);
			i = j;
		}
		return res;
	}

	public static void main(String[] args) {
		// MergeIntervals a = new MergeIntervals();
		// int n = 6;
		// Random ran = new Random();
		// Interval in;
		// ArrayList<Interval> intervals = new ArrayList<Interval>();
		// for (int i = 0; i < n; ++i) {
		// in = new Interval(ran.nextInt(20), ran.nextInt(20));
		// intervals.add(in);
		// }
		// a.merge(intervals);
	}
}
